package com.cat.dataStructure;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/find-two-non-overlapping-sub-arrays-each-with-target-sum/
 * @create 2025/8/19 11:18
 * @since JDK17
 */

public class Solution34 {
    public int minSumOfLengths(int[] arr, int target) {
        int ans = Integer.MAX_VALUE / 2, n = arr.length, sum = 0;
        int[] min = new int[n + 1];
        Arrays.fill(min, Integer.MAX_VALUE / 2);    // 全部填入最小值
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, n);
        for (int i = n - 1; i >= 0; i--) {
            sum += arr[i];  // 后缀和
            if (map.containsKey(sum - target)) {
                min[i] = map.get(sum - target) - i;
            }
            min[i] = Math.min(min[i], min[i + 1]);
            map.put(sum, i);
        }
        map.clear();
        map.put(0, -1);
        sum = 0;
        for (int i = 0, t; i < n; i++) {
            sum += arr[i];
            if (map.containsKey(sum - target)) {
                t = i - map.get(sum - target);
                ans = Math.min(t + min[i + 1], ans);
            }
            map.put(sum, i);
        }

        return ans == Integer.MAX_VALUE / 2 ? -1 : ans;
    }
}
